package org.example.l2;

import org.junit.jupiter.api.Test;

import java.util.*;

public class Other {

    public void sortColors(int[] nums) {
        int len = nums.length, p0 = 0, p2 = len - 1;
        for (int i = 0; i <= p2; i++) {
            while (i <= p2 && nums[i] == 2) {
                swap(nums, p2, i);
                p2--;
            }
            if (nums[i] == 0) {
                swap(nums, i, p0);
                p0++;
            }
        }
    }

    void swap(int[] nums,
              int i,
              int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    @Test
    void aa() {
        int[][] from = IntHelper.from("[[1,2,3,4],[5,6,7,8],[9,10,11,12]]\n");
        spiralOrder(from);
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int len1 = matrix.length, len2 = matrix[0].length;
        int left = 0, right = len2 - 1, top = 0, bottom = len1 - 1;
        for (; left <= right && bottom >= top; ) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;

            for (int i = right; i >= left && top <= bottom; i--) {
                res.add(matrix[bottom][i]);
            }
            bottom--;
            for (int i = bottom; i >= top && left <= right; i--) {
                res.add(matrix[i][left]);
            }
            left++;
        }

        return res;
    }

    @Test
    void ab() {
        partitionLabels("ababcbacadefegdehijhklij");
    }

    public List<Integer> partitionLabels(String s) {
        char[] chars = s.toCharArray();
        int[] last = new int[26];
        for (int i = 0; i < chars.length; i++) {
            last[chars[i] - 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < chars.length; i++) {
            end = Math.max(end, last[chars[i] - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }

    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        int len1 = grid.length, len2 = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        for (int i = 0; i < len1; ++i) {
            for (int j = 0; j < len2; ++j) {
                if (grid[i][j] == 2) {
                    int code = i * len2 + j;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / len2, c = code % len2;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < len1 && 0 <= nc && nc < len2 && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * len2 + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }
        for (int[] row : grid) {
            for (int v : row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}